<!DOCTYPE html>
<html class="writer-html5" lang="en" >
<head>
    <meta charset="utf-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
      <link rel="shortcut icon" href="../../img/favicon.ico" />
    <title>图与树 - 咩咩的笔记</title>
    <link rel="stylesheet" href="../../css/theme.css" />
    <link rel="stylesheet" href="../../css/theme_extra.css" />
        <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/10.5.0/styles/github.min.css" />
    
      <script>
        // Current page data
        var mkdocs_page_name = "\u56fe\u4e0e\u6811";
        var mkdocs_page_input_path = "\u79bb\u6563\u6570\u5b66\\9-\u56fe\u4e0e\u6811.md";
        var mkdocs_page_url = null;
      </script>
    
    <script src="../../js/jquery-3.6.0.min.js" defer></script>
    <!--[if lt IE 9]>
      <script src="../../js/html5shiv.min.js"></script>
    <![endif]-->
      <script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/10.5.0/highlight.min.js"></script>
      <script>hljs.initHighlightingOnLoad();</script> 
</head>

<body class="wy-body-for-nav" role="document">

  <div class="wy-grid-for-nav">
    <nav data-toggle="wy-nav-shift" class="wy-nav-side stickynav">
    <div class="wy-side-scroll">
      <div class="wy-side-nav-search">
          <a href="../.." class="icon icon-home"> 咩咩的笔记
        </a><div role="search">
  <form id ="rtd-search-form" class="wy-form" action="../../search.html" method="get">
      <input type="text" name="q" placeholder="Search docs" aria-label="Search docs" title="Type search term here" />
  </form>
</div>
      </div>

      <div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="Navigation menu">
              <ul>
                <li class="toctree-l1"><a class="reference internal" href="../..">主页</a>
                </li>
              </ul>
              <p class="caption"><span class="caption-text">笔记</span></p>
              <ul class="current">
                  <li class="toctree-l1"><a class="reference internal" href="#">线性代数</a>
    <ul>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/0-%E5%89%8D%E8%A8%80/">0-前言</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/1-%E7%BA%BF%E6%80%A7%E6%96%B9%E7%A8%8B%E7%BB%84/">1-线性方程组</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/2-%E7%9F%A9%E9%98%B5%E4%BB%A3%E6%95%B0/">2-矩阵代数</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/3-%E8%A1%8C%E5%88%97%E5%BC%8F/">3-行列式</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/4-%E5%90%91%E9%87%8F%E7%A9%BA%E9%97%B4/">4-向量空间</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/5-%E7%89%B9%E5%BE%81%E5%80%BC%E4%B8%8E%E7%89%B9%E5%BE%81%E5%90%91%E9%87%8F/">5-特征值与特征向量</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/6-%E6%AD%A3%E4%BA%A4%E6%80%A7%E4%B8%8E%E6%9C%80%E5%B0%8F%E4%BA%8C%E4%B9%98/">6-正交性与最小二乘</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/7-%E5%AF%B9%E7%A7%B0%E9%98%B5%E4%B8%8E%E4%BA%8C%E6%AC%A1%E5%9E%8B/">7-对称阵与二次型</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/8-%E5%90%91%E9%87%8F%E7%A9%BA%E9%97%B4%E7%9A%84%E5%87%A0%E4%BD%95/">8-向量空间的几何</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/%E9%99%84%E5%BD%95A-3Blue1Brown%E7%AC%94%E8%AE%B0/">附录A-3Blue1Brown笔记</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/%E9%99%84%E5%BD%95B-%E9%9B%B6%E7%A9%BA%E9%97%B4%E4%B8%8E%E5%88%97%E7%A9%BA%E9%97%B4%E7%9A%84%E5%AF%B9%E6%AF%94/">附录B-零空间与列空间的对比</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/%E9%99%84%E5%BD%95C-%E9%80%86%E7%9F%A9%E9%98%B5%E5%AE%9A%E7%90%86/">附录C-逆矩阵定理</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0/%E9%99%84%E5%BD%95D-%E6%80%9D%E7%BB%B4%E5%AF%BC%E5%9B%BE/">附录D-思维导图</a>
                </li>
    </ul>
                  </li>
                  <li class="toctree-l1"><a class="reference internal" href="#">数字电路</a>
    <ul>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%95%B0%E5%AD%97%E7%94%B5%E8%B7%AF/1.%20%E4%BB%8B%E7%BB%8D/">介绍</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%95%B0%E5%AD%97%E7%94%B5%E8%B7%AF/2.%20%E6%95%B0%E5%AD%97%E7%B3%BB%E7%BB%9F%E3%80%81%E8%BF%90%E7%AE%97%E5%92%8C%E7%BC%96%E7%A0%81/">数字系统、运算和编码</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%95%B0%E5%AD%97%E7%94%B5%E8%B7%AF/3.%20%E9%80%BB%E8%BE%91%E9%97%A8/">逻辑门</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%95%B0%E5%AD%97%E7%94%B5%E8%B7%AF/4.%20%E5%B8%83%E5%B0%94%E4%BB%A3%E6%95%B0/">布尔代数</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%95%B0%E5%AD%97%E7%94%B5%E8%B7%AF/5.%20%E7%BB%84%E5%90%88%E9%80%BB%E8%BE%91%E5%88%86%E6%9E%90/">组合逻辑分析</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%95%B0%E5%AD%97%E7%94%B5%E8%B7%AF/6.%20%E7%BB%84%E5%90%88%E9%80%BB%E8%BE%91%E5%8A%9F%E8%83%BD%E6%A8%A1%E5%9D%97/">组合逻辑功能模块</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%95%B0%E5%AD%97%E7%94%B5%E8%B7%AF/7.%20%E9%94%81%E5%AD%98%E5%99%A8%E3%80%81%E8%A7%A6%E5%8F%91%E5%99%A8%E5%92%8C%E5%AE%9A%E6%97%B6%E5%99%A8/">锁存器、触发器和定时器</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%95%B0%E5%AD%97%E7%94%B5%E8%B7%AF/8.%20%E7%A7%BB%E4%BD%8D%E5%AF%84%E5%AD%98%E5%99%A8/">移位寄存器</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%95%B0%E5%AD%97%E7%94%B5%E8%B7%AF/9.%20%E8%AE%A1%E6%95%B0%E5%99%A8/">计数器</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%95%B0%E5%AD%97%E7%94%B5%E8%B7%AF/10.%20%E5%82%A8%E5%AD%98%E5%99%A8/">储存器</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%95%B0%E5%AD%97%E7%94%B5%E8%B7%AF/11.%20%E6%A8%A1%E6%95%B0%E8%BD%AC%E6%8D%A2/">模数转换</a>
                </li>
    </ul>
                  </li>
                  <li class="toctree-l1 current"><a class="reference internal current" href="#">离散数学</a>
    <ul class="current">
                <li class="toctree-l2"><a class="reference internal" href="../2-%E5%91%BD%E9%A2%98%E9%80%BB%E8%BE%91/">命题逻辑</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../3-%E4%B8%80%E9%98%B6%E9%80%BB%E8%BE%91/">一阶逻辑</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../4-%E8%AF%81%E6%98%8E%E6%96%B9%E6%B3%95/">证明方法</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../5-%E9%9B%86%E5%90%88/">集合</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../6-%E5%85%B3%E7%B3%BB/">关系</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../7-%E5%87%BD%E6%95%B0/">函数</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../8-%E8%AE%A1%E6%95%B0%E4%B8%8E%E7%BB%84%E5%90%88/">计数与组合</a>
                </li>
                <li class="toctree-l2 current"><a class="reference internal current" href="./">图与树</a>
    <ul class="current">
    <li class="toctree-l3"><a class="reference internal" href="#_2">图的基本概念</a>
        <ul>
    <li class="toctree-l4"><a class="reference internal" href="#_3">图的连通性</a>
    </li>
    <li class="toctree-l4"><a class="reference internal" href="#_4">图的表示与储存</a>
    </li>
    <li class="toctree-l4"><a class="reference internal" href="#_5">无向图的遍历</a>
    </li>
        </ul>
    </li>
    <li class="toctree-l3"><a class="reference internal" href="#_6">树的基础知识</a>
        <ul>
    <li class="toctree-l4"><a class="reference internal" href="#_7">无向树的定义</a>
    </li>
    <li class="toctree-l4"><a class="reference internal" href="#_8">根树的定义</a>
    </li>
    <li class="toctree-l4"><a class="reference internal" href="#_9">树的遍历</a>
    </li>
        </ul>
    </li>
    <li class="toctree-l3"><a class="reference internal" href="#_10">带权图及其应用</a>
        <ul>
    <li class="toctree-l4"><a class="reference internal" href="#_11">带权图的最短距离</a>
    </li>
    <li class="toctree-l4"><a class="reference internal" href="#_12">带权图的最小生成树</a>
    </li>
    <li class="toctree-l4"><a class="reference internal" href="#_13">哈夫曼树</a>
    </li>
        </ul>
    </li>
    <li class="toctree-l3"><a class="reference internal" href="#_14">一些特殊的图</a>
        <ul>
    <li class="toctree-l4"><a class="reference internal" href="#_15">平面图</a>
    </li>
    <li class="toctree-l4"><a class="reference internal" href="#_16">欧拉图</a>
    </li>
    <li class="toctree-l4"><a class="reference internal" href="#_17">哈密顿图</a>
    </li>
        </ul>
    </li>
    </ul>
                </li>
    </ul>
                  </li>
                  <li class="toctree-l1"><a class="reference internal" href="#">计算机组成原理</a>
    <ul>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/1.%20%E8%AE%A1%E7%AE%97%E6%9C%BA%E6%A6%82%E8%A7%88/">计算机概览</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/2.%20%E6%8C%87%E4%BB%A4/">指令</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/3.%20%E8%AE%A1%E7%AE%97%E6%9C%BA%E4%B8%AD%E7%9A%84%E8%BF%90%E7%AE%97/">计算机中的运算</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/4.%20MIPS%20CPU%E8%AE%BE%E8%AE%A1/">MIPS CPU设计</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/5.%20%E5%AD%98%E5%82%A8%E5%99%A8%E5%B1%82%E6%AC%A1%E7%BB%93%E6%9E%84/">存储器层次结构</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/6.%20%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%B3%BB%E7%BB%9F%E6%80%BB%E7%BA%BF/">计算机系统总线</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/7.%20%E8%BE%93%E5%85%A5%E8%BE%93%E5%87%BA%E7%B3%BB%E7%BB%9F/">输入输出系统</a>
                </li>
    </ul>
                  </li>
                  <li class="toctree-l1"><a class="reference internal" href="#">计算机组成原理实验</a>
    <ul>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E5%AE%9E%E9%AA%8C/1/1/">加法器</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E5%AE%9E%E9%AA%8C/2/2/">有限状态机</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E5%AE%9E%E9%AA%8C/3/3/">MIPS指令集1</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E5%AE%9E%E9%AA%8C/4/4/">MIPS指令集2</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E5%AE%9E%E9%AA%8C/5/5/">存储器实验</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E5%AE%9E%E9%AA%8C/6/6/">寄存器堆与 ALU 设计实验</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E5%AE%9E%E9%AA%8C/7/7/">存储器与控制器实验</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E5%AE%9E%E9%AA%8C/8/8/">单周期处理器实验</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E5%AE%9E%E9%AA%8C/9/9/">多周期处理器实验</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E5%AE%9E%E9%AA%8C/10/10/">多周期处理器综合性开放实验</a>
                </li>
    </ul>
                  </li>
                  <li class="toctree-l1"><a class="reference internal" href="#">概率论</a>
    <ul>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%A6%82%E7%8E%87%E8%AE%BA/1.%20%E6%A6%82%E7%8E%87%E8%AE%BA%E7%9A%84%E5%9F%BA%E6%9C%AC%E6%A6%82%E5%BF%B5/">概率论的基本概念</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%A6%82%E7%8E%87%E8%AE%BA/2.%20%E9%9A%8F%E6%9C%BA%E5%8F%98%E9%87%8F%E5%8F%8A%E5%85%B6%E5%88%86%E5%B8%83/">随机变量及其分布</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%A6%82%E7%8E%87%E8%AE%BA/3.%20%E5%A4%9A%E7%BB%B4%E9%9A%8F%E6%9C%BA%E5%8F%98%E9%87%8F%E5%8F%8A%E5%85%B6%E5%88%86%E5%B8%83/">多维随机变量及其分布</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%A6%82%E7%8E%87%E8%AE%BA/4.%20%E9%9A%8F%E6%9C%BA%E5%8F%98%E9%87%8F%E7%9A%84%E6%95%B0%E5%AD%97%E7%89%B9%E5%BE%81/">随机变量的数字特征</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%A6%82%E7%8E%87%E8%AE%BA/5.%20%E5%A4%A7%E6%95%B0%E5%AE%9A%E5%BE%8B%E5%8F%8A%E4%B8%AD%E5%BF%83%E6%9E%81%E9%99%90%E5%AE%9A%E7%90%86/">大数定律及中心极限定理</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%A6%82%E7%8E%87%E8%AE%BA/6.%20%E6%A0%B7%E6%9C%AC%E5%8F%8A%E6%8A%BD%E6%A0%B7%E5%88%86%E5%B8%83/">样本及抽样分布</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%A6%82%E7%8E%87%E8%AE%BA/7.%20%E5%8F%82%E6%95%B0%E4%BC%B0%E8%AE%A1/">参数估计</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E6%A6%82%E7%8E%87%E8%AE%BA/8.%20%E5%81%87%E8%AE%BE%E9%AA%8C%E8%AF%81/">假设验证</a>
                </li>
    </ul>
                  </li>
                  <li class="toctree-l1"><a class="reference internal" href="#">信号与系统</a>
    <ul>
                <li class="toctree-l2"><a class="reference internal" href="../../%E4%BF%A1%E5%8F%B7%E4%B8%8E%E7%B3%BB%E7%BB%9F/1.%20%E4%BF%A1%E5%8F%B7%E4%B8%8E%E7%B3%BB%E7%BB%9F/">信号与系统</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E4%BF%A1%E5%8F%B7%E4%B8%8E%E7%B3%BB%E7%BB%9F/2.%20%E7%BA%BF%E6%80%A7%E6%97%B6%E4%B8%8D%E5%8F%98%E7%B3%BB%E7%BB%9F/">线性时不变系统</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E4%BF%A1%E5%8F%B7%E4%B8%8E%E7%B3%BB%E7%BB%9F/3.%20%E5%91%A8%E6%9C%9F%E4%BF%A1%E5%8F%B7%E7%9A%84%E5%82%85%E9%87%8C%E5%8F%B6%E7%BA%A7%E6%95%B0%E8%A1%A8%E7%A4%BA/">周期信号的傅里叶级数表示</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E4%BF%A1%E5%8F%B7%E4%B8%8E%E7%B3%BB%E7%BB%9F/4.%20%E8%BF%9E%E7%BB%AD%E6%97%B6%E9%97%B4%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2/">连续时间傅里叶变换</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E4%BF%A1%E5%8F%B7%E4%B8%8E%E7%B3%BB%E7%BB%9F/5.%20%E7%A6%BB%E6%95%A3%E6%97%B6%E9%97%B4%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2/">离散时间傅里叶变换</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E4%BF%A1%E5%8F%B7%E4%B8%8E%E7%B3%BB%E7%BB%9F/6.%20%E4%BF%A1%E5%8F%B7%E4%B8%8E%E7%B3%BB%E7%BB%9F%E7%9A%84%E6%97%B6%E5%9F%9F%E5%92%8C%E9%A2%91%E5%9F%9F%E7%89%B9%E6%80%A7/">信号与系统的时域和频域特性</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E4%BF%A1%E5%8F%B7%E4%B8%8E%E7%B3%BB%E7%BB%9F/7.%20%E9%87%87%E6%A0%B7/">采样</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E4%BF%A1%E5%8F%B7%E4%B8%8E%E7%B3%BB%E7%BB%9F/9.%20%E6%8B%89%E6%99%AE%E6%8B%89%E6%96%AF%E5%8F%98%E6%8D%A2/">拉普拉斯变换</a>
                </li>
                <li class="toctree-l2"><a class="reference internal" href="../../%E4%BF%A1%E5%8F%B7%E4%B8%8E%E7%B3%BB%E7%BB%9F/10.%20z%E5%8F%98%E6%8D%A2/">z变换</a>
                </li>
    </ul>
                  </li>
              </ul>
      </div>
    </div>
    </nav>

    <section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">
      <nav class="wy-nav-top" role="navigation" aria-label="Mobile navigation menu">
          <i data-toggle="wy-nav-top" class="fa fa-bars"></i>
          <a href="../..">咩咩的笔记</a>
        
      </nav>
      <div class="wy-nav-content">
        <div class="rst-content"><div role="navigation" aria-label="breadcrumbs navigation">
  <ul class="wy-breadcrumbs">
    <li><a href="../.." class="icon icon-home" aria-label="Docs"></a> &raquo;</li>
          <li>笔记 &raquo;</li>
          <li>离散数学 &raquo;</li>
      <li>图与树</li>
    <li class="wy-breadcrumbs-aside">
    </li>
  </ul>
  <hr/>
</div>
          <div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
            <div class="section" itemprop="articleBody">
              
                <h1 id="_1">图的基础知识</h1>
<h2 id="_2">图的基本概念</h2>
<ul>
<li>
<p>（定义9.1）<strong>无向图</strong> 是二元组<code>G＝(V,E)</code>，其中V是非空集，称为图的<strong>顶点集</strong>，它的元素称为G的<strong>顶点</strong>(vertex)或节点；E称为图的<strong>边集</strong>，它的元素称为G的<strong>边</strong>(edge)，且每条边<span class="arithmatex">\(e\in E\)</span>，都<strong>关联</strong>两个顶点u和v，这两个顶点称为边e的两个<strong>端点</strong>，也称边e连接这两个端点，通常将边e记为<code>e=(u,v)</code>或<code>e=(v,u)</code></p>
</li>
<li>
<p>（定义9.1）<strong>有向图</strong> 是二元组<code>G＝(V,E)</code>，非空集V是图的顶点集，它的元素称为G的顶点或节点；E是图的边集，它的元素称为G的<strong>有向边</strong>，且每条边都有一个顶点u作为它的<strong>起点</strong>，还有一个顶点v作为它的<strong>终点</strong>，通常记为<code>e=&lt;u,v&gt;</code>。有向图的<strong>基图</strong>是不考虑边的方向而得到的无向图。</p>
</li>
<li>
<p>如果一个图既有有向边又有无向边，则这个图称为<strong>混合图</strong>，本章不研究。</p>
</li>
<li>一些特殊的图：<ul>
<li>含有n个顶点的图称为<strong>n阶图</strong></li>
<li>不含边的图称为<strong>零图</strong></li>
<li>只有一个顶点的图称为<strong>平凡图</strong></li>
<li>顶点集为空集的图称为<strong>空图</strong></li>
<li>使用符号标记了顶点和边的图称为<strong>标定图</strong></li>
</ul>
</li>
<li>
<p>（定义9.3）对于图：</p>
<ul>
<li>若e连接顶点u,v，则称e <strong>关联</strong> u和v</li>
<li>若u,v间有边则称u与v <strong>邻接</strong>，若进一步区分u是起点v是终点，则可称u <strong>邻接到</strong> v而v <strong>邻接与</strong> u</li>
<li>若两条边关联同一个顶点，则称这两边<strong>邻接</strong></li>
</ul>
</li>
<li>
<p>（定义9.4）对于图：</p>
<ul>
<li><strong>环</strong>是关联同一个顶点的边</li>
<li><strong>重边</strong>是关联顶点相同的两条边（有向边的起点终点要相同）</li>
<li><strong>简单图</strong>是不含环和重边的图</li>
</ul>
</li>
<li>
<p>（定义9.5）</p>
<ul>
<li>对于无向图 <span class="arithmatex">\(G=(V,E)\)</span> 中的一个顶点<span class="arithmatex">\(v\in V\)</span>，v的<strong>度数</strong>d(v)是关联v的边的条数，其中关联v的环要计算两遍</li>
<li>对于有向图，进一步区分<strong>入度</strong><span class="arithmatex">\(d^-(v)\)</span>等于以v为终点的有向边条数，<strong>出度</strong><span class="arithmatex">\(d^+(v)\)</span>等于以v为起点的有向边条数，度数等于入度和出度之和</li>
</ul>
</li>
<li>
<p>无向图中度数为一的顶点称为<strong>悬挂顶点</strong>，与悬挂顶点关联的边称为<strong>悬挂边</strong>。度数为0的顶点称为<strong>孤立顶点</strong></p>
</li>
<li>
<p>（定理9.1）<strong>握手定理</strong>：无向图中所有顶点的度数之和等于边数的两倍<span class="arithmatex">\(\sum_{d\in V}d(v)=2|E|\)</span>；有向图中所有顶点的出度和等于入度和等于边数<span class="arithmatex">\(\sum_{d\in V}d^-(v)=\sum_{d\in V}d^+(v)=|E|\)</span>。</p>
</li>
<li>
<p><strong>奇度顶点</strong>是度数为奇数的顶点，<strong>偶度顶点</strong>是度数为偶数的顶点</p>
</li>
<li>（推论9.2）任何图的奇度顶点个数是偶数</li>
<li>（定义9.6）<strong>最小度</strong> <span class="arithmatex">\(\delta(G)\)</span> 等于度数最小的顶点的度数；<strong>最大度</strong><span class="arithmatex">\(\Delta(G)\)</span>等于度数最大的顶点的度数</li>
<li>（定义9.7）<strong>k正则图</strong>是任意顶点度数都等于k的图；<strong>完全图</strong>是任意两个顶点间都有边的<em>简单图</em>；特别地，有n个顶点的完全图被称为n阶完全图，记为<span class="arithmatex">\(K_n\)</span></li>
<li>
<p>更多特殊的图：</p>
<ul>
<li><strong>圈</strong>是按序号首尾相连的简单图</li>
<li><strong>轮图</strong>是在圈的基础上增加一个邻接所有其他顶点的顶点</li>
<li><strong>立方体图</strong><span class="arithmatex">\(Q_n\)</span>是具有<span class="arithmatex">\(2^n\)</span>个顶点的图，其中每个顶点可用二进制编号，使得两个顶点有边当且仅当他们的二进制编号只有一位不同</li>
<li><strong>二部图</strong>是顶点集可被划分为两个部分<span class="arithmatex">\(V_1\)</span>和<span class="arithmatex">\(V_2\)</span>，使得每个部分内的点互不关联的图，二部图也称<strong>偶图</strong>或<strong>二分图</strong>，它对顶点集的划分称为<strong>二部划分</strong>（定义9.8）</li>
<li><strong>完全二部图</strong>是<span class="arithmatex">\(V_1\)</span>的任意顶点和<span class="arithmatex">\(V_2\)</span>的任意顶点都恰有一边相连的二部图</li>
</ul>
</li>
<li>
<p>（定义9.9）如果G'=(V',E')的顶点集和边集都是G=(V,E)对应集的子集，则称G'是G的<strong>子图</strong>；特别地，如果V'=V，则称G'是G的<strong>生成子图</strong>；如果子图缺少的边都是因为缺少顶点造成的，也就是<span class="arithmatex">\(E'=\{e\in E | e=(u,v)且u\in V'且v\in V'\}\)</span>，则称G'是G的<strong>导出子图</strong></p>
</li>
<li>
<p>一些对图的操作</p>
<ul>
<li><strong>删除顶点集</strong>G-V'：删除包含在V'中的顶点，并移除关联这些顶点的边</li>
<li><strong>删除边集</strong>G-E'：删除包含在E'中的边</li>
<li><strong>删除子图</strong>G-G'：删除G在其子图G'中的所有边</li>
<li><strong>边的收缩</strong>G\e：删除e并合并e关联的两个顶点（合并指的是用新顶点代替原来两个顶点，新顶点关联原来两个顶点关联的所有边）</li>
<li><strong>添加新边</strong>G+(u,v)：字面意思</li>
</ul>
</li>
<li>n解简单图G的<strong>补图</strong><span class="arithmatex">\(\bar G=K_n-G\)</span></li>
<li>（定义9.11）对于图<span class="arithmatex">\(G=(V,E)\)</span>和 <span class="arithmatex">\(G'=(V',E')\)</span> ，如果存在双函数 <span class="arithmatex">\(f:V\to V'\)</span> ，满足：对E的任意边<span class="arithmatex">\(e=(u,v)\)</span>，E'存在唯一的边 <span class="arithmatex">\(e'=(f(u),f(v))\)</span> ，而且对E'的任意边 <span class="arithmatex">\(e'=(u',v')\)</span>，E存在唯一的边<span class="arithmatex">\(e=(f^{-1}(u'),f^{-1}(v'))\)</span> ，则称G和G'同构，记为G~G'</li>
</ul>
<h3 id="_3">图的连通性</h3>
<ul>
<li>
<p>（定义9.12）对无向图G：</p>
<ul>
<li><strong>通路</strong><span class="arithmatex">\(\Gamma=v_0e_1v_1e_2\cdots e_nv_n\)</span>是G的顶点和边的交替序列，且对任意<span class="arithmatex">\(1\leq i\leq n\)</span>有<span class="arithmatex">\(e_i=(v_{i-1},v_i)\)</span>。这时称<span class="arithmatex">\(v_0\)</span>和<span class="arithmatex">\(v_n\)</span>是<span class="arithmatex">\(\Gamma\)</span>的两个端点，n是<span class="arithmatex">\(\Gamma\)</span>的长度。如果还满足<span class="arithmatex">\(v_0=v_n\)</span>，则称<span class="arithmatex">\(\Gamma\)</span>是<strong>回路</strong></li>
<li><strong>简单通路</strong>或<strong>简单回路</strong>中“简单”指不含重复边</li>
<li><strong>初级通路</strong>或<strong>初级回路</strong>中“初级”指不含重复顶点</li>
<li>初级通路又称<strong>路径</strong>，初级回路又称<strong>圈</strong></li>
</ul>
</li>
<li>
<p>（定义9.13）对于有向图，<strong>有向通路</strong>相当于在无向图的通路基础上加入方向性，其他有向定义类似</p>
</li>
<li>（引理9.3）对于有n个顶点的图，若u,v间存在通路，则u,v间一定存在以u,v为端点的长度小于等于n-1的初级通路</li>
<li>（推论9.4）对于有n个顶点的图，若u存在到其自身的回路，则一定存在从u到其自身的长度小于等于n的初级回路</li>
<li>（定义9.14）对于无向图G，若u,v间存在通路，则称他们是<strong>可达的</strong>，并约定顶点到其自身是可达的；在V上定义关系<span class="arithmatex">\(\leftrightarrow\subseteq V\times V\)</span>，<span class="arithmatex">\(u\leftrightarrow v\)</span>当且仅当u和v是可达的，则<span class="arithmatex">\(\leftrightarrow\)</span>是等价关系，称V关于<span class="arithmatex">\(\leftrightarrow\)</span>的等价类<span class="arithmatex">\([u]_\leftrightarrow\subseteq V\)</span>导出的子图为G的<strong>连通分支</strong>，一般记G的连通分支数为<span class="arithmatex">\(p(G)\)</span>。若p(G)=1，则称G是<strong>连通无向图</strong>，或连通图。</li>
<li>（引理9.5）设无向图G(V,E)是简单图，|V|=n，|E|=m。若G是连通图，则<span class="arithmatex">\(m\geq n-1\)</span></li>
<li>
<p>（定义9.15）设G=(V,E)是无向图，<span class="arithmatex">\(V'\subset V\)</span>是顶点集V的真子集，若V'满足：</p>
<ol>
<li>G-V'的连通分支比G多</li>
<li>只删除V'中的某些顶点及关联的边不会增加图的连通分支数<br />
则称V'是图的<strong>点割集</strong>。若点割集只有一个顶点，则称该顶点为<strong>割点</strong></li>
</ol>
</li>
<li>
<p>（定义9.16）设G(V,E)是连通无向图，|V|=n，且完全图<span class="arithmatex">\(K_n\)</span>不是G的子图。将图G的顶点数最少的点割集的顶点数称为它的<strong>点连通度</strong>，简称<strong>连通度</strong>，记为<span class="arithmatex">\(\kappa(G)\)</span>。约定完全图<span class="arithmatex">\(K_n\)</span>的点连通度为n-1，非连通图的点连通度为0，。若<span class="arithmatex">\(\kappa(G)\geq k\)</span>，则称G是k连通图</p>
</li>
<li>
<p>（定义9.15）设G=(V,E)是无向图，<span class="arithmatex">\(E'\subset E\)</span>是边集E的真子集，若E'满足：</p>
<ol>
<li>G-E'的连通分支比G多</li>
<li>只删除E'中的某些边不会增加图的连通分支数<br />
则称V'是图的<strong>边割集</strong>。若边割集只有一条边，则称该边为<strong>割边</strong>，或<strong>桥</strong>。</li>
</ol>
</li>
<li>
<p>（定义9.16）设G(V,E)是连通无向图。将图G的边数最少的边割集的边数称为它的<strong>边连通度</strong>，记为<span class="arithmatex">\(\lambda(G)\)</span>。约定非连通图的边连通度为0，。若<span class="arithmatex">\(\lambda(G)\geq r\)</span>，则称G是r边连通图</p>
</li>
<li>
<p>（定义9.19）设G=(V,E)是有向图，u和v是G的两个顶点，若存在以u为起点，v为终点的有向通路，则称u<strong>可达</strong>v，记为<span class="arithmatex">\(u\to v\)</span>。进一步记<span class="arithmatex">\(u\to v\)</span>且<span class="arithmatex">\(v\to u\)</span>为<span class="arithmatex">\(u\leftrightarrow v\)</span>。约定总有<span class="arithmatex">\(u\leftrightarrow u\)</span>。</p>
</li>
<li>
<p>若有向图G中任意两个顶点u,v都有<span class="arithmatex">\(u\leftrightarrow v\)</span>，则称G是<strong>强连通有向图</strong>；若有向图G中任意两个顶点u,v至少有<span class="arithmatex">\(u\to v\)</span>或<span class="arithmatex">\(v\to u\)</span>之一成立，则称G是<strong>单向连通图</strong>；若有向图G的基图是无向连通图，则称G是**弱连通图。</p>
</li>
<li>
<p>有向图G是强连通的当且仅当G存在经过每个顶点至少一次的有向回路</p>
</li>
</ul>
<h3 id="_4">图的表示与储存</h3>
<ul>
<li>（定义9.20）设G=(V,E)是有向图，其中<span class="arithmatex">\(V=\{v_1,v_2,\cdots,v_n\}\)</span>,<span class="arithmatex">\(E=\{e_1,e_2,\cdots,e_m\}\)</span>。则G的<strong>关联矩阵</strong><span class="arithmatex">\(M=[m_{ij}]\)</span>是<span class="arithmatex">\(n\times m\)</span>的矩阵，对任意的<span class="arithmatex">\(1\leq i\leq n,1\leq j\leq m\)</span>有：</li>
</ul>
<div class="arithmatex">\[
m_{ij}=\left\{
\begin{aligned}
&amp;1  &amp;若v_i是e_j的起点\\
&amp;-1 &amp;若v_i是e_j的终点\\
&amp;0  &amp;否则
\end{aligned}
\right.
\]</div>
<p>类似地，无向图G的<strong>关联矩阵</strong><span class="arithmatex">\(M=[m_{ij}]\)</span>定义为：若<span class="arithmatex">\(v_i\)</span>是<span class="arithmatex">\(e_j\)</span>的端点则<span class="arithmatex">\(m_{ij}=1\)</span>，否则<span class="arithmatex">\(m_{ij}=0\)</span></p>
<blockquote>
<p>也就是说关联矩阵每一列都是一条边，对应行表示该边是否与某顶点关联等</p>
</blockquote>
<ul>
<li>（定义9.21）设G=(V,E)是有向图，其中<span class="arithmatex">\(V=\{v_1,v_2,\cdots,v_n\}\)</span>。G的<strong>邻接矩阵</strong><span class="arithmatex">\(A=[a_{ij}]\)</span>是<span class="arithmatex">\(n\times n\)</span>的矩阵，对任意<span class="arithmatex">\(1\leq i \leq n\)</span>,<span class="arithmatex">\(1\leq j\leq n\)</span>，有：</li>
</ul>
<div class="arithmatex">\[
a_{ij}=以v_i为起点、v_j为终点的有向边的条数
\]</div>
<p>类似地，无向边G的<strong>邻接矩阵</strong><span class="arithmatex">\(A=[a_{ij}]\)</span>定义为：<span class="arithmatex">\(a_{ij}\)</span>是以v_i和v_j为端点的无向边条数。</p>
<ul>
<li>
<p>对G的邻接矩阵A，使用普通的矩阵乘法得到的<span class="arithmatex">\(A^k\)</span>表示G的任意两个顶点之间的长度为k的（有向）通路条数</p>
</li>
<li>
<p>令矩阵<span class="arithmatex">\(B=\sum_{i=1}^{n-1}A^i\)</span>，则B的元素<span class="arithmatex">\(b_{ij}\)</span>给出顶点<span class="arithmatex">\(v_i\)</span>和<span class="arithmatex">\(v_j\)</span>之间长度不超过n的（有向）通路条数。定义<strong>可达矩阵</strong><span class="arithmatex">\(P=[p_{ij}]\)</span>，对角线均为1（顶点到自己总是可达的），其余位置若<span class="arithmatex">\(b_{ij}\geq 1\)</span>则<span class="arithmatex">\(p_{ij}=1\)</span>。</p>
</li>
<li>
<p><strong>邻接表</strong>可以用来表示一个简单有向图或简单无向图。若一个简单有向图有n个顶点，则它的邻接表有n行，每一行给出一个顶点的邻接顶点列表，即以这个顶点为起点的有向边的终点的列表。类似地，如果一个简单无向图有n个顶点，它的邻接表也是n行，每一行给出一个顶点的邻接顶点列表，即以这个顶点为一个端点的无向边的另一个端点的列表。</p>
</li>
</ul>
<h3 id="_5">无向图的遍历</h3>
<ul>
<li>图的<strong>遍历</strong>或称<strong>搜索</strong>是指从图的某个顶点出发，沿着一些边访问所有顶点；遍历有两种思路：<strong>深度优先搜索</strong>（先深搜索）和<strong>广度优先搜索</strong>（先广搜索）</li>
<li>深搜需要用栈（后进先出）S记录已经访问过且需要回溯的顶点序列，用集合T记录所有访问过的顶点。算法从往T和S中加入一个起始点开始，不断地尝试沿着S的栈顶顶点的边找其邻接且不在T的顶点，如果找到了就入栈并将新顶点记录到T中，否则栈顶顶点出栈，这样一直持续到栈被清空；如果图中还有顶点未加入T（非连通图才会出现），则随便找个未加入T的顶点加入T和S重复算法。实际实现中可以用递归算法实现，算法复杂度为<span class="arithmatex">\(O(n^2)\)</span>。</li>
<li>广搜需要用队列（先进先出）Q记录尚未访问过其所有相邻顶点的顶点，用集合T记录所有访问过的顶点。算法从往T和Q中加入一个起始点开始，不断地从队列中取出顶点并访问其所有邻接顶点，将访问到的未加入T的顶点加入T和Q，如此重复直到队列清空；如果图中还有顶点未加入T就随便选一个未加入T的放入T和Q。算法复杂度为<span class="arithmatex">\(O(n^2)\)</span></li>
</ul>
<h2 id="_6">树的基础知识</h2>
<h3 id="_7">无向树的定义</h3>
<ul>
<li>（定义9.22）连通且没有回路的简单无向图称为<strong>无向树</strong>。无向树中度数为1的顶点成为<strong>树叶</strong>，度数大于或等于2的顶点称为<strong>分支点</strong>。只有一个顶点的简单图称为<strong>平凡树</strong>。含有多个无回路的连通分支的简单无向图称为<strong>森林</strong></li>
<li>（定理9.7、9.8）设简单无向图G有n个顶点m条边，以下命题等价：<ol>
<li>G是树</li>
<li>G的任意两个顶点之间存在唯一的通路</li>
<li>G连通且任意边都是桥</li>
<li>G无回路，但在任意两个不相邻顶点之间加一条新边，则得到唯一一个且含新边的回路</li>
<li>G无回路且m=n-1</li>
<li>G连通且m＝n-1</li>
</ol>
</li>
</ul>
<h3 id="_8">根树的定义</h3>
<ul>
<li>（定义9.23）若一个有向图的基图是树，则称这个图是<strong>有向树</strong>。若有向树T有且仅有一个顶点r的入度为0，则称T是以r为<strong>根</strong>的<strong>根树</strong>。我们也将根树中的顶点称为<strong>节点</strong>。根树中出度为0的顶点称为<strong>叶子</strong>，出度不为0的顶点称为<strong>内部顶点</strong></li>
<li>（引理9.9）设T=(V,E)是以顶点r为根的根树，且<span class="arithmatex">\(|V|&gt;1\)</span>，则除r以外的顶点入度都为1。进一步，r到任意其他顶点都有唯一的有向通路</li>
<li>（定义9.24）设T＝(V,E)是根树，u,v是T的两个顶点。若存在有向边<span class="arithmatex">\(e=\langle u,v\rangle\in E\)</span>则称u是v的<strong>父亲</strong>，而v是u的<strong>儿子</strong>；如果顶点u和v有相同的父亲，则称u是v的<strong>兄弟</strong>。若存在u到v的一条有向通路，则称u是v的<strong>祖先</strong>，而v是u的<strong>后代</strong>。T的顶点u及其所有后代顶点导出的T的子图称为T的以u为根的<strong>子树</strong>。设T的根是r，则对T的任意顶点u，从r到u的唯一通路的长度称为u的<strong>层数</strong>。定义T的<strong>高度</strong>是从r到T的叶子的最长通路的长度</li>
<li>（定义9.25）如果根树T的每个顶点的出度都不大于m，则称T是<strong>m元树</strong>；如果每个顶点的出度不是0就是m，则称T是<strong>满m元树</strong>或<strong>正则m元树</strong>。如果满m元树T的每片叶子的层数都等于树高，则称T是<strong>完全m元树</strong>。如果高度为h的m元树T的每片叶子要么是h，要么是h－1，则称T是<strong>平衡m元树</strong></li>
<li>如果一棵树的每个顶点的儿子顶点都按照某个顺序排列，则称这棵根树为<strong>有序根树</strong>。有序二元树通常就称为<strong>二元树</strong>或<strong>二叉树</strong>，它的每个顶遍历点的第一个儿子通常称为<strong>左儿子</strong>，第二个儿子通常称为<strong>右儿子</strong>。以左儿子为根的子树称为<strong>左子树</strong>，以右儿子为根的子树称为<strong>右子树</strong>。</li>
</ul>
<h3 id="_9">树的遍历</h3>
<p>树的遍历一般从根开始，可采用先深或先广。</p>
<ul>
<li>先广遍历在树中其实就是一层层往下遍历</li>
<li>先深遍历分前序、中序和后序<ol>
<li>前序顶点入栈后先执行操作再继续深入</li>
<li>中序则是入栈后先遍历第一个儿子再执行操作最后遍历其他儿子</li>
<li>后序是顶点入栈后先遍历完所有儿子（也就是出栈前）再执行操作。</li>
</ol>
</li>
<li>对于抽象语法树，对其进行前序、中序和后序遍历输出可分别得到表达式的<strong>前缀</strong>、<strong>中缀</strong>和<strong>后缀</strong>形式。表达式的前缀形式也称为<strong>波兰记号</strong>，后缀形式也称为<strong>逆波兰记号</strong></li>
</ul>
<h2 id="_10">带权图及其应用</h2>
<h3 id="_11">带权图的最短距离</h3>
<ul>
<li>（定义9.26）<strong>带权有向图</strong>就是每条有向边都被赋一个非负实数作为边的权的简单有向图</li>
<li>（定义9.27）带权有向图的<strong>距离矩阵</strong>是一个n阶方阵，定义类似于可达矩阵，第i行第j列表示第i个顶点到第j个顶点的边的权（若没有边则为正无穷）</li>
<li>有向路径的<strong>带权同路长度</strong>等于构成通路边的权之和，v到u的最小的带权通路长度最短的通路称为v到u的<strong>最短通路</strong>，该通路长度称为v到u的<strong>最短距离</strong><blockquote>
<p>在定义9.26简单图和非负边权的条件下，最短通路又被称为<strong>最短路径</strong></p>
</blockquote>
</li>
<li>（定理9.12）若<span class="arithmatex">\(v_1,\cdots,k_{k-1},v_k\)</span>是<span class="arithmatex">\(v_1\)</span>到<span class="arithmatex">\(v_k\)</span>的最短路径，则<span class="arithmatex">\(v_1,\cdots,v_{k-1}\)</span>是<span class="arithmatex">\(v_1\)</span>到<span class="arithmatex">\(v_{k-1}\)</span>的最短路径</li>
<li>
<p><strong>最短路径的Djikstra算法</strong><br />
    定义三个集合或数组：<br />
        1. S记录尚未求得最短路径的顶点的集合<br />
        2. U是以顶点编号为下标的数组，<span class="arithmatex">\(u_i\)</span>表示<span class="arithmatex">\(v_1\)</span>到<span class="arithmatex">\(v_i\)</span>的最短距离<br />
        3. Q是以顶点编号为下标的数组，<span class="arithmatex">\(q_i\)</span>表示<span class="arithmatex">\(v_1\)</span>到<span class="arithmatex">\(v_i\)</span>的最短通路的直接前驱结点编号（也就是到终点前的一个顶点）  </p>
<p>算法过程：<br />
    1. 初始化：最开始只有<span class="arithmatex">\(v_1\)</span>已求得最短路，也就是S包含<span class="arithmatex">\(v_1\)</span>以外的所有顶点（为了实现方便，v_1暂时也归入S），<span class="arithmatex">\(u_1=0\)</span>，U的其他项为无穷<br />
    2. 更新最短路：从S中的顶点中选择其在U中记录的最短距离最小的顶点<span class="arithmatex">\(v_x\)</span>（特别地，第一次更新必然取得<span class="arithmatex">\(v_1\)</span>），将其从S中取出，并利用该顶点中转尝试更新其他顶点的最短路（术语<em>松弛</em>），也就是对于所有尚未确定最短路的顶点<span class="arithmatex">\(v_y\)</span>，如果<span class="arithmatex">\(u_x+d_{xy}&lt;u_y\)</span>，更新<span class="arithmatex">\(u_y\)</span>和<span class="arithmatex">\(q_y\)</span><br />
    3. 重复过程2，直到S中没有元素</p>
<p>算法分析：<br />
1. 该算法可以根据给定的简单带权有向图和某一给定起点，求出该起点到其他任意点的最短路径和对应最短距离<br />
2. 算法复杂度在不优化的情况下为<span class="arithmatex">\(O(n^2)\)</span><br />
3. 算法有效性证明思路是对于任意时间点，先证明S中的顶点对应记录的最短路必然是在利用已确定最短路的顶点为中间顶点情况下的最短路（用归纳法），再证明第二步中选出的顶点必然已确定最短路（用反证法）即可</p>
<h3 id="_12">带权图的最小生成树</h3>
</li>
<li>
<p>（定义9.30）若无向树T=(V,E')是连通无向图G=(V,E)的生成子图（顶点集相同，边集是子集），则T是G的<strong>生成树</strong>或<strong>支撑树</strong></p>
</li>
<li>（定义9.31）一个带权连通图G的所有生成树中树枝权值之和最小的生成树称为G的<strong>最小生成树</strong></li>
<li><strong>Kruskal算法</strong>：不断从G中取出权最小的边加入到生成树中，并保证不构成回路（若构成回路则直接舍弃这条边）。添加n-1次后即可得到一棵最小生成树。</li>
<li><strong>Prim算法</strong>：先从V中任取一点加入到V‘中，然后从一端点在V‘另一端点在V-V'的边中选择权最小的加入到生成树中，添加n-1次即可得到一棵最小生成树。</li>
</ul>
<h3 id="_13">哈夫曼树</h3>
<ul>
<li>（定义9.32）给定有k个叶子的二叉树T=(V,E)，若k个叶子分别赋以非负实数权<span class="arithmatex">\(w_1,w_2,\cdots,w_k\)</span>，则称T是<strong>带权二叉树</strong>。若T的k个叶子对应的层数分别是<span class="arithmatex">\(l_1,l_2,\cdots,l_k\)</span>，则称<span class="arithmatex">\(w(T)=\sum^k_{i=1}l_i\cdot w_i\)</span>为<strong>带权二叉树T的权</strong>。称有最小权的带权二叉树为<strong>最优二叉树</strong>，也称为<strong>哈夫曼树</strong></li>
<li>哈夫曼算法：将所有带权叶子放入集合中。不断取出集合中权最小的两个节点，将两个节点用一个根节点合并，并把根节点放回集合中。一直重复直到集合中只有一个节点，该节点展开就是哈夫曼树。</li>
</ul>
<div class="admonition note">
<p class="admonition-title">Note<p>最后根的权并不一定等于树的权</p>
</p>
</div>
<ul>
<li>记哈夫曼树所有的左节点为0，右节点为1，这样每条从根节点到叶子的唯一通路对应了该叶子的唯一编码，利用该哈夫曼树就可以实现对数据的不等长编解码压缩</li>
<li>串的<strong>前缀</strong>是从第一个字符开始的子串（不包含本身）；<strong>前缀码</strong>是一个串集合，该集合内任意两元素都不互为前缀；若前缀码中的串都由两种符号组成，则其称为<strong>二元前缀码</strong></li>
</ul>
<div class="admonition note">
<p class="admonition-title">Note<p>要对不等长编码的文件进行译码，这种编码必须是前缀码，哈夫曼编码是前缀码</p>
</p>
</div>
<h2 id="_14">一些特殊的图</h2>
<h3 id="_15">平面图</h3>
<ul>
<li>（定义9.35）<strong>可平面图</strong>是可以给出一种画法使得任意两条边交点必然是顶点的图，这种图满足定义画法的图像就叫<strong>平面图</strong></li>
<li>（定义9.36）平面图的<strong>面</strong>或<strong>域</strong> R是若干边包围的、内部不包含顶点和边的区域，所有包围边组成的回路被称为该面的<strong>边界</strong>，回路长度被称为该面的<strong>度</strong>，记为deg(R)。由平面图的边包围且无穷大的面被称为平面图的<strong>外部面</strong>，其他面被称为<strong>外部面</strong></li>
</ul>
<div class="admonition note">
<p class="admonition-title">Note<p>面里面可以有“隔边“，隔边算两遍；环包围的区域也算面</p>
</p>
</div>
<ul>
<li>平面图的所有面的度之和等于边数的两倍</li>
<li><strong>欧拉公式</strong>：设连通平面图G有n个顶点m条边d个面，则<span class="arithmatex">\(n-m+d=2\)</span></li>
<li>（定理9.16）设G是连通的平面图，且G的各面度数大于或等于l，则G的边数m与顶点数n满足</li>
</ul>
<div class="arithmatex">\[
m\leq\frac{l}{l-2}(n-2)
\]</div>
<ul>
<li>（推论）定义<span class="arithmatex">\(g(G)\)</span>是图G长度最小的回路的长度，称为图G的<strong>围长</strong>，若连通平面图G的围长大于等于l，则</li>
</ul>
<div class="arithmatex">\[
m\leq\frac{l}{l-2}(n-2)
\]</div>
<ul>
<li>（定义9.37）<strong>极大平面图</strong>是满足任意两个不相邻顶点之间加一条新边都会得到非平面图的简单平面图</li>
<li>（引理9.18）：<ol>
<li>极大平面图是连通图</li>
<li>极大平面图没有桥</li>
<li>极大平面图的每个面都有三条边组成</li>
<li>极大平面图面数的三倍等于边数的两倍</li>
<li>极大平面图的任意一个顶点与相邻顶点必构成一个回路</li>
<li>若极大平面图的顶点数大于等于4，则其最小度大于等于3</li>
</ol>
</li>
<li>（定理9.19）设极大平面图G有n个顶点m条边d个面，则<span class="arithmatex">\(m=3n-6\)</span>且<span class="arithmatex">\(d=2n-4\)</span></li>
<li>（推论9.20）设简单平面图G有n个顶点m条边d个面，则<span class="arithmatex">\(m\leq3n-6\)</span>且<span class="arithmatex">\(d\leq2n-4\)</span></li>
<li>（引理9.21）完全图<span class="arithmatex">\(K_5\)</span>和完全二部图<span class="arithmatex">\(K_{3,3}\)</span>都不是平面图</li>
<li>（定义9.38）<span class="arithmatex">\(K_5\)</span>和<span class="arithmatex">\(K_{3,3}\)</span>分别记为<span class="arithmatex">\(K^{(1)}\)</span>和<span class="arithmatex">\(K^{(2)}\)</span>图，在<span class="arithmatex">\(K^{(1)}\)</span>和<span class="arithmatex">\(K^{(2)}\)</span>图上任意增加一些度数为2的顶点之后得到的图称为<span class="arithmatex">\(K^{(1)}\)</span>和<span class="arithmatex">\(K^{(2)}\)</span>型图，统称为K型图</li>
<li>（定理9.22）<strong>库拉图斯基定理</strong>：图G是可平面的当且仅当G不存在K型子图<blockquote>
<p>这只在理论上可行，实际要判断一个图是否可平面的算法比较复杂</p>
</blockquote>
</li>
</ul>
<h3 id="_16">欧拉图</h3>
<ul>
<li>（定义9.39）无向连通图G的一条经过所有边的简单回路称为G的<strong>欧拉回路</strong>，经过所有边的简单通路称为<strong>简单通路</strong>；含有欧拉回路的图称为<strong>欧拉图</strong>，含有欧拉通路的图称为<strong>半欧拉图</strong></li>
<li>（定理9.23）无向连通图存在欧拉回路的充要条件是所有顶点的度数都为偶数</li>
<li>（推论9.24）若无向连通图G只有两个度数为奇数的顶点，则G存在欧拉通路</li>
<li>欧拉图与一笔画问题和中国邮递员问题相关，书上有相关介绍，略</li>
</ul>
<h3 id="_17">哈密顿图</h3>
<ul>
<li>（定义9.40）无向图的一条经过全部顶点的初级回路称为<strong>哈密顿回路</strong>，经过全部顶点的初级通路称为<strong>哈密顿通路</strong>。存在哈密顿回路的无向图称为<strong>哈密顿图</strong>，存在哈密顿通路的图称为<strong>半哈密顿图</strong></li>
<li>（定义9.41）无向图的<strong>极长通路</strong>是两端点至于该通路顶点相邻的简单通路，如果他还是初级通路，则称为<strong>极长初级通路</strong></li>
<li>（定理9.25）如果n阶简单图G的任意两个顶点的度数之和大于或等于<span class="arithmatex">\(n-1\)</span>，这里<span class="arithmatex">\(n\geq 2\)</span>，则G存在哈密顿通路<blockquote>
<p>这是充分条件，充要条件还没找到</p>
</blockquote>
</li>
<li>（推论9.26）若n（大于等于3）阶简单图G的任意两顶点度数之和大于或等于n，则G存在哈密顿回路</li>
</ul>
              
            </div>
          </div><footer>
    <div class="rst-footer-buttons" role="navigation" aria-label="Footer Navigation">
        <a href="../8-%E8%AE%A1%E6%95%B0%E4%B8%8E%E7%BB%84%E5%90%88/" class="btn btn-neutral float-left" title="计数与组合"><span class="icon icon-circle-arrow-left"></span> Previous</a>
        <a href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/1.%20%E8%AE%A1%E7%AE%97%E6%9C%BA%E6%A6%82%E8%A7%88/" class="btn btn-neutral float-right" title="计算机概览">Next <span class="icon icon-circle-arrow-right"></span></a>
    </div>

  <hr/>

  <div role="contentinfo">
    <!-- Copyright etc -->
  </div>

  Built with <a href="https://www.mkdocs.org/">MkDocs</a> using a <a href="https://github.com/readthedocs/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>.
</footer>
          
        </div>
      </div>

    </section>

  </div>

  <div class="rst-versions" role="note" aria-label="Versions">
  <span class="rst-current-version" data-toggle="rst-current-version">
    
    
      <span><a href="../8-%E8%AE%A1%E6%95%B0%E4%B8%8E%E7%BB%84%E5%90%88/" style="color: #fcfcfc">&laquo; Previous</a></span>
    
    
      <span><a href="../../%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/1.%20%E8%AE%A1%E7%AE%97%E6%9C%BA%E6%A6%82%E8%A7%88/" style="color: #fcfcfc">Next &raquo;</a></span>
    
  </span>
</div>
    <script>var base_url = '../..';</script>
    <script src="../../js/theme_extra.js" defer></script>
    <script src="../../js/theme.js" defer></script>
      <script src="../../javascripts/mathjax.js" defer></script>
      <script src="https://fastly.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js" defer></script>
      <script src="../../search/main.js" defer></script>
    <script defer>
        window.onload = function () {
            SphinxRtdTheme.Navigation.enable(true);
        };
    </script>

</body>
</html>
